package shortestpath.bellmanford;

import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import shortestpath.Edge;
import shortestpath.Graph;
import shortestpath.Node;
import shortestpath.ShortestPathFinder;
import _general.problem.ShortestPath;

public class BellmanFord<T extends Node> extends ShortestPath implements ShortestPathFinder<T> {

	public BellmanFord() {	
		setName("Bellman-Ford Algorithm");
	}
	
	@Override
	public void start() {
		this.findShortestPath((Graph<T>) g, (T) g.getField(0, 0), (T) g.getField(g.getX()-1, g.getY()-1));
	}
	
	@Override
	public List<T> findShortestPath(Graph<T> g, T start, T destination) {
		final Map<T, Integer> distances = new HashMap<T, Integer>();
		final Map<T, T> predecessors = new HashMap<T, T>();
		for (T node : g.getNodes()) {
			distances.put(node, node.equals(start) ? 0 : Integer.MAX_VALUE);
		}

		for (int i = 1; i < g.getNodes().size(); i++) {
			for (Edge<T> edge : g.getEdges()) {
				final Long distance = (long) distances.get(edge.getStart())
						+ edge.getWeight();
				if (distance < distances.get(edge.getEnd())) {
					distances.put(edge.getEnd(), distance.intValue());
					predecessors.put(edge.getEnd(), edge.getStart());
				}
			}
		}

		for (Edge<T> edge : g.getEdges()) {
			if (distances.get(edge.getStart()) + edge.getWeight() < distances
					.get(edge.getEnd())) {
				throw new IllegalStateException(
						"Der Graph enth�lt einen Kreis negativer L�nge");
			}
		}

		return this.getShortestPath(predecessors, destination);
	}

	private List<T> getShortestPath(final Map<T, T> predecessors,
			final T destination) {
		final List<T> result = new LinkedList<T>();
		T current = destination;
		while (current != null) {
			result.add(current);
			current = predecessors.get(current);
		}
		Collections.reverse(result);
		return result;
	}

}